Spanning tree protocols are well-known in the art for providing path redundancy within a network while preventing undesirable loops. Examples of conventional spanning tree protocols include, but may not be limited to, Spanning Tree Protocol (STP), Rapid Spanning Tree Protocol (RSTP) and Multiple Spanning Tree Protocol (MSTP).
When a change in topology occurs within the network, such as the failure of a link or the addition of a bridge to the topology, a spanning tree protocol performs a process known as convergence or re-convergence. The convergence process involves computing a new spanning tree topology, electing a root bridge known to all bridges, and computing the roles and states of ports on all bridges. Spanning tree protocols typically use two primary states for bridge ports—forwarding and discarding. A port that is designated as “Alternate” is a port that is currently blocked for a given spanning tree instance. An alternate port will have a state of discarding, so that information does not pass through the port. Through this convergence process and the designation of alternate ports, a loop free topology is provided for. Once convergence is finished, the network node topology is rendered stable and the implemented spanning tree protocol is in steady state, exchanging only “Hello” messages about every 2 seconds to confirm that each link is performing properly.
Avoiding loops in a network is an important task of spanning tree protocols. When loops do occur, the communication of information via an affected bridge or bridges quickly becomes very confusing and demanding of the affected bridges' processing resources. For example, a Media Control Access (MAC) address is a unique identifier that forms the basis for most layer 2 networking. When a loop occurs, a bridge may see its own MAC address on two different ports at the same time, thus misleading the forwarding engine as to which destination port packets should be sent.
Loops in a network may also adversely impact the functionality and/or efficiency of Source Learning Protocol, a processing module that maintains a Layer 2 bridging table (i.e., the Filtering database). This Layer 2 bridging table associates any learned, given MAC address to a given port in a given VLAN. In doing so, it allows Layer 2 hardware forwarding processing to take place (i.e., sending a given frame to the correct port). In the presence of a loop, each time a station is learned on a port, if that same MAC address has been seen before on another port, the Source Learning Protocol software carries out MAC Address Movement processing whereby it updates the Layer 2 bridging table according to the most recent information available (i.e., finding an old MAC address, deleting it and creating a new MAC address).
Bridge Protocol Data Units (BPDUs) are frames that are sent by bridge protocol software to communicate with adjacent bridges. Conventional spanning tree protocols such as STP, RSTP and MSTP inhibit flooding or bridging of BPDUs by hardware. However, conventional spanning tree protocols are typically implemented in software because of the complexity of the associated algorithmic computations. The reliance on software for STP processing means that the more nodes there are in a given topology, the longer it takes to re-converge. Each time a BPDU is received, it has to be processed by the spanning tree protocol software before it can be transmitted in turn on one or several ports.
Software processing time to process and send one or several BPDUs can be as low as 10-50 milliseconds if the software is not overloaded, but the processing time can increase dramatically when software is getting congested. Thus, with conventional implementations of spanning tree protocols, it is not practical or realistic to guaranty sub-50 millisecond re-convergence times typically required in carrier space networks.